//二叉树中序遍历的迭代实现
//尤其注意 在搜索二叉树中 中序遍历的序列是递增的！

class Solution
{
public:
    vector<int> res;

    vector<int> inorderTraversal(TreeNode *root)
    {
        inOrder(root);
        return res;
    }

    void inOrder(TreeNode *root)
    {
        stack<TreeNode *> node;

        while (root || !node.empty())
        {
            while (root)
            {
                //一路向左！
                node.push(root);
                root = root->left;
            }

            if (!node.empty())
            {
                root = node.top();
                node.pop();
                res.push_back(root->val);
                root = root->right;
            }
        }
    }
};